package com.leecode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huangzhigao
 * @Date: 2022/3/28 22:32
 */
public class leecode560 {
    public int subarraySum(int[] nums, int k) {
        int[] preSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int res = 0;
        for (int i = 1; i < preSum.length; i++) {
            for (int j = 0; j < i; j++) {
                if (preSum[i] - preSum[j] == k) {
                    res++;
                }
            }
        }
        return res;
    }

    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        int start = 0;
        for (int end = 0; end < chars.length; end++) {
            if (map.containsKey(chars[end])) {
                start = Math.max(start, map.get(chars[end]));
            }
            map.put(chars[end], end + 1);
            res = Math.max(res, end - start + 1);
        }
        return res;

    }

    /**
     * 前缀和问题
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum1(int[] nums, int k) {
        int pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }


    public int lengthOfLongestSubstring1(String s) {
        char[] chars = s.toCharArray();
        int res = 0;
        int left = 0;
        int right = 0;
        int[] window = new int[256];
        while (right < chars.length) {
            char c = chars[right];
            window[c]++;
            right++;
            while (window[c] > 1) {
                char b = chars[left];
                window[b]--;
                left++;
            }
            res = Math.max(res,right-left+1);
        }
        return res;

    }
}
